package com.sicheng.蓝桥.练习题.基础图论;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/12 9:57
 */
public class BellmanFord {
    /**
     * https://www.acwing.com/problem/content/description/855/
     * Bellman - ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。
     * 其原理为连续进行松弛，在每次松弛时把每条边都更新一下，
     * 若在 n-1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。
     * (通俗的来讲就是：假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，
     * 通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新)
     * <p>
     * for n次
     * 记录上一轮的dist->back
     * for 所有边 a,b,w (松弛操作)
     * dist[b] = min(dist[b],back[a] + w)
     * <p>
     * 注意：back[] 数组是上一次迭代后 dist[] 数组的备份，
     * 由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点
     * <p>
     * <p>
     * bellman - ford算法擅长解决有边数限制的最短路问题
     */
    static class Node {
        int a;
        int b;
        int w;

        public Node(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }

    static int N = 510;
    static int M = 10010;
    static int n;
    static int INF = 0x3f3f3f3f;
    static int k, m;
    private static final Node[] nodes = new Node[M];
    private static final int[] dist = new int[N];
    private static final int[] back = new int[N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        k = scanner.nextInt();

        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int w = scanner.nextInt();
            nodes[i + 1] = new Node(a, b, w);
        }


        Arrays.fill(dist, 0, n + 1, INF);
        dist[1] = 0;
        for (int i = 0; i < k; i++) {

            System.arraycopy(dist, 0, back, 0, n + 1);
            for (int j = 1; j <= m; j++) {
                Node node = nodes[j];
                dist[node.b] = Math.min(dist[node.b], back[node.a] + node.w);
            }
        }
        if (dist[n] > INF >> 1)
            System.out.println("impossible");
        else
            System.out.println(dist[n]);

    }
}
